package m202405.d16;

import java.util.HashSet;
import java.util.List;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/16 16:40
 */
public class Q139 {

    //s=leet  wd=[le,et]
    //dp[] = true
    //dp[l] = dp[]&&wd.contains(l)
    //dp[le]= (dp[]&&wd.contains[le]) || (dp[l]&&wd.contains(e))
    //dp[lee] = (dp[]&&wd.contains[lee]) || (dp[l]&&wd.contains(ee)) || (d[le]&&wd.contains(e))
    //dp[leet] = (dp[]&&wd.contains[leet]) || (dp[l]&&wd.contains(eet)) || (d[le]&&wd.contains(et)) || (d[lee]&&wd.contains(t))
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        HashSet<String> set = new HashSet<>(wordDict);
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
